package com.chapter4.graph.mst;

import java.util.PriorityQueue;

import com.chapter1.basic.queue.Queue;

/**
 * 
* @ClassName: LazyPrimMST 
* @Description: lazy prim最小生成树算法 
* @author minjun
* @date 2015年3月8日 下午9:17:39 
*
 */
public class LazyPrimMST {
	
	//是否访问过
	private boolean[] marked;
	
	//树
	private Queue<Edge> mst;
	
	//存储距离为1的边
	private PriorityQueue<Edge> pq;
	
	//权重
	private double weight;

	public LazyPrimMST(WeightEdgeGraph g){
		int len=g.V();
		marked=new boolean[len];
		mst=new Queue<Edge>();
		pq=new PriorityQueue<Edge>();
		//将0设置成已访问节点,并将与指定节点相连的边加入到优先队列
		visit(g,0);
		//获取优先队列的最小权重，并加入到树中
		while(!pq.isEmpty()&&mst.size()<len-1){
			//取出权重最小的边
			Edge edge=pq.poll();
			int a=edge.either();
			int b=edge.other(a);
			//如果两个端点都已经被访问过，则忽略掉
			if(marked[a]&&marked[b]) continue;
			//否则，将该边添加到队列中
			mst.offer(edge);
			//将重量计入
			weight+=edge.weight();
			//并将新加入的节点设置成已访问节点
			if(!marked[a]) visit(g, a);
			if(!marked[b]) visit(g, b);
		}
	}
	
	private void visit(WeightEdgeGraph g, int v) {
		//访问指定节点
		marked[v]=true;
		for(Edge edge:g.adj(v)){
			int o=edge.other(v);
			System.out.println(marked[o]+","+v+"-"+o);
			//如果该边不在树中，表示该边中除开v的另外一个端点没有被访问过，那么将该边加入到优先队列
			if(!marked[o]){
				pq.offer(edge);
			}
		}
	}

	public Iterable<Edge> edges(){
		return mst;
	}
	
	public double weight(){
		return weight;
	}
	
}
